package third

import "strconv"

/*
	输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。
	比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

	示例 1:

	输入: n = 1
	输出: [1,2,3,4,5,6,7,8,9]
	说明：

	用返回一个整数列表来代替打印
	n 为正整数

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
func PrintNumbers(n int) []int {
	return printNumbers(n)
}

// 要求1~n中所有十进制数实际上就是求n个0-9的全排列、也就是给定一个字符串、长度为n、每一位都从1取到9
// n没有指定范围、所以这里用字符串可以防止越界
func printNumbers(n int) []int {
	result := make([]int, 0)
	printNumberRecurse(n, "", &result)
	return result[1:]
}

func printNumberRecurse(n int, curs string, result *[]int) {
	if len(curs) == n {
		cr, _ := strconv.Atoi(curs)
		*result = append(*result, cr)
		return
	}
	for i := 0; i <= 9; i++ {
		printNumberRecurse(n, curs+strconv.Itoa(i), result)
	}
}
